Cache memory has long been used in computing systems to decrease the memory access time for the central processing unit (CPU) thereof. Cache memory may be used to store only program instructions, only data, or both program instructions and data. A cache memory is typically a relatively high speed, relatively small memory in which active portions of program instructions and/or data are placed therein, generally only temporarily (i.e., for a short period of time until overwritten). The cache memory, which is typically located between the CPU and main memory in a computing system, is typically faster than main memory by a factor of 5 to 10 and typically approaches the speed of the CPU itself. By keeping the most frequently accessed instructions and/or data in the high speed cache memory, the average memory access time will approach the access time of the cache.
The active program instructions and data may be kept in a cache memory by utilizing the phenomenon known as "locality of reference". The locality of reference phenomenon recognizes that most computer program instruction processing proceeds in a sequential fashion with multiple loops, and with the CPU repeatedly referring to a set of instructions in a particular localized area of memory. Thus, loops and subroutines tend to localize the references to memory for fetching instructions. Similarly, memory references to data also tend to be localized, because table lookup routines or other iterative routines typically repeatedly refer to a small portion of memory.
In view of the phenomenon of locality of reference, a small, high speed cache memory may be provided for storing a block of data and/or instructions from main memory which are presently being processed. Although the cache is only a small fraction of the size of main memory, a large fraction of memory requests will locate data or instructions in the cache memory because of the locality of reference property of programs. In a CPU which has a relatively small, relatively high speed cache memory and a relatively large, relatively low speed main memory, the CPU examines the cache when a memory access instruction is processed. If the desired word (data or program instruction) is found in cache, it is read from the cache. If the word is not found in cache, the main memory is accessed to read that word, and a block of words containing that word is transferred from main memory to cache memory. Accordingly, future references to memory are likely to find the required words in the cache memory because of the locality of reference property.
The performance of cache memory is frequently measured in terms of a "hit ratio". When the CPU references memory and finds the word in cache, it produces a "hit". If the word is not found in cache, then it is in main memory and it counts as a "miss". The ratio of the number of hits divided by the total CPU references to memory (i.e. hits plus misses) is the hit ratio. Experimental data obtained by running representative programs has indicated that hit ratios of 0.9 (90%) or higher are needed to justify the search time to determine a hit or miss because the search time is added to the normal memory access time in the case of a miss. With such high hit ratios, the memory access time of the overall data processing system approaches the memory access time of the cache memory, and may improve the memory access time of main memory by a factor of 5 to 10 or more. Accordingly, the average memory access time of the computing system may be improved considerably by the use of a cache.
Cache "misses" are generally undesirable, and, as the number of misses increases, memory access time generally increases and system performance generally decreases. Therefore, decreasing the number of misses, or, in the alternative, increasing the number of hits per access attempts, generally results in a decrease in access time and improvement in system performance.
A number of alternatives have been used in an effort to improve the hit ratio with respect to cache memory, including allowing system control over the use of the cache memory. One alternative approach is to store only instructions in the cache or to store only data in the cache. Another alternative approach is to enlarge the size of cache memory so that additional program instructions, data or both program instructions and data may be stored in the cache memory at any given time.
Unfortunately, these prior art alternatives may still produce problems of their own. For example, the enlargement of cache memory size may require additional storage space which may ultimately negatively impact system performance with respect to other operations even though access time may be decreased.